package oj.hot100;

public class 回文子串 {
    //动态规划
    public int countSubstrings(String ss) {
        char[] s = ss.toCharArray();
        int n = s.length,ret = 0;
        boolean[][] dp = new boolean[n][n];
        for(int i = n-1;i >= 0;i--) {
            for(int j = n-1;j >= i;j--) {
                if(s[i] != s[j]) {
                    dp[i][j] = false;
                }else {
                    if(i+1 ==j || i == j) {
                        dp[i][j] = true;
                    }else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                if(dp[i][j]) ret++;
            }
        }
        return ret;
    }
    //中心扩展算法
    public int countSubstringsEx(String ss) {
        char[] s = ss.toCharArray();
        int n = s.length,ret = 0;
        for(int i = 0;i < n;i++) {
            //子串字符为奇数个
            int left = i,right = i;
            while(left >= 0 && right < n && s[left] == s[right]) {
                left--;
                right++;
                ret++;
            }
            left = i;
            right = i+1;
            //子串字符为偶数个
            while(left >= 0 && right < n && s[left] == s[right]) {
                left--;
                right++;
                ret++;
            }
        }
        return ret;
    }
}
